The invention relates to technology for implementing electronic design automation tools, and in particular, design tools for performing design rule checks (DRC) for an integrated circuit (“IC”) design.
An IC is a small electronic device typically formed from semiconductor material. Each IC contains a large number of electronic components, e.g., transistors, that are wired together to create a self-contained circuit device. The components and wiring on the IC are materialized as a set of geometric shapes that are placed and routed on the chip material. During placement, the location and positioning of each geometric shape corresponding to an IC component are identified on the IC layers. During routing, a set of routes are identified to tie together the geometric shapes for the electronic components.
Spacing rules are established to ensure that adequate spacing exists between any two objects/shapes on the IC design. These rules are usually established by the foundry that will produce the IC chip. A DRC tool is used to check for violations of spacing rules on the IC design.
“Width-dependent” spacing rules may also be established for an IC design. With modern, advanced technology, the minimum spacing between two metals on the IC design may be relative to the width of the two metal shapes. For example, if the metal width is X, then the spacing between this metal with the next space to the adjacent metal may need to be distance d. If the metal width is 2×, then the spacing between this metal with the next space to the adjacent metal may need to be wider, e.g., a distance of 1.5d.
DRC tools may use a process called “undersize-oversize” to address this problem. By first undersizing the metal shapes, all metals below a designated size are eliminated. The remaining metals are then restored to their original sizes by using the oversizing process.
FIG. 1 illustrates an application of this technique. Shown are two metal objects 102a and 104. Object 102a has a width of “3a” and object 104 has a width of “a”. During the undersize process, each object is reduced by a common shrinking factor, e.g., “a/2”. After the undersize process, any object that falls below a minimum number is eliminated from the design.
Here, assume that the dotted shape within object 102a shows the remaining size of this object after the undersize process. Further assume that object 104 will be too small and will be eliminated after the undersize process. Therefore, remaining after the undersize process is an object 102b that is a reduced version of object 102a. Note that in the undersizing process, the angled corners for object 102a have not been retained in object 102b. 
Next, an oversizing process is applied to restore object 102b back to its original size. Object 102c is shown restored back to the original size of object 102a. However, it is noted that the angled corners of object 102a have not been restored. An additional step is performed to add the original angled corners to produce the layout having object 102d, which has the size and shape of the original metal object 102a. 
As is evident, a series of several passes (e.g., 4) is required to perform this type of process. With modern designs, it is likely that there will be multiple segments (e.g., three segments) to the design, and each segment will undergo the same process. This multiplies the number of passes through the design to perform this type of process (up to 12 passes, which is four passes for the undersize-oversize process multiplied by three for each of the three segments). Since each pass through the design consumes a significant amount of system resources, the more passes it takes to perform the process, the greater the negative impact to the system. In a modern IC design having many millions of objects to process, this type of process having requiring many passes through a design could consume an excessive amount of system resources.
Therefore, it is highly desirable to implement a method and mechanism for performing a spacing rule DRC check that does not require an excessive number of passes through the IC design. Embodiments of the invention provide an improved method and mechanism for performing a spacing rule DRC check that does not require an excessive number of passes through the IC design. In one embodiment, a two-pass approach is employed to perform a spacing check. In an embodiment, polygons are associated with a family of related polygons.